//并查集，先连普通点，如果一个集合只有一个病毒连着才有贡献，一个病毒可以拯救它单独连着的集合，计算每个病毒能拯救的个数
class Solution {
public:
    vector<int> fa;
    vector<int> sz;

    int find(int x)
    {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }

    void Union(int u,int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return;
        if(sz[u] > sz[v]) swap(u,v);
        fa[u] = v;
        sz[v] += sz[u];
    }
    vector<bool> vis;
    vector<int> f;
    vector<int> cnt;
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        fa.resize(n);
        sz.resize(n);
        vis.resize(n,false);
        f.resize(n,0);
        cnt.resize(n,0);

        for(auto& e : initial)
        {
            vis[e] = true;
        }
        for(int i = 0;i < n;i++)
        {
            fa[i] = i;
            sz[i] = 1;
        }

        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < n;j++)
            {
                if(graph[i][j] == 1 && !vis[i] && !vis[j])
                {
                    Union(i,j);
                }
            }
        }

        unordered_set<int> s;
        unordered_map<int,vector<int>> mp;//集合 to 病毒
        for(int i = 0;i < initial.size();i++)
        {
            int curv = initial[i];
            s.clear();
            for(int j = 0;j < n;j++)
            {
                if(curv == j) continue;
                if(graph[curv][j] == 0)continue;
                if(vis[j]) continue;
                if(s.count(find(j))) continue;
                f[find(j)]++;
                mp[find(j)].push_back(curv);
                s.insert(find(j));
            }
        }

        // for(int i = 0;i < n;i++)
        // {
        //     cout << f[i] << " ";
        // }
        // cout << endl;

        for(int i = 0;i < n;i++)
        {
            if(fa[i] == i && !vis[i])
            {
                if(f[i] != 1)continue;
                cnt[mp[i][0]] += sz[i];
            }
        }
        // for(int i = 0;i < n;i++)
        // {
        //     cout << cnt[i] << " ";
        // }

        int mxsz = -1;
        int idx = initial[0];
        for(auto& cur : initial)
        {
            if(cnt[cur] > mxsz || (cnt[cur] == mxsz && cur < idx))
            {
                mxsz = cnt[cur];
                idx = cur;
            }
        }
        return idx;
    }
};

/* [[1,0,0,0,0,0,0,0,0],
    [0,1,0,0,0,0,0,0,1],
    [0,0,1,0,0,0,0,0,0],
    [0,0,0,1,0,0,0,0,1],
    [0,0,0,0,1,0,1,1,1],
    [0,0,0,0,0,1,0,0,1],
    [0,0,0,0,1,0,1,1,0],
    [0,0,0,0,1,0,1,1,0],
    [0,1,0,1,1,1,0,0,1]]*/